/**
 * 
 */
package sg.edu.nus;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @author Christian
 *
 */
public class CompleteMiner implements RoleMiner {

	private Map<Integer, Integer[]> initRoles;
	private Map<Integer, Integer> initRolesCount;
	private Map<Integer, Integer[]> genRoles;
	private Map<Integer, Integer> genRolesCount;
	private TreeMap<Integer, List<Integer>> countSortedResult;
	
	public CompleteMiner(List<Integer[]> usersWithPermissions, int initRolePriority) {
		initRoles = new HashMap<Integer, Integer[]>();
		initRolesCount = new HashMap<Integer, Integer>();
		genRoles = new HashMap<Integer, Integer[]>();
		genRolesCount = new HashMap<Integer, Integer>();
		// mine roles
		mineRoles(usersWithPermissions);
		// create sorted result
		countSortedResult = getSortedResult(initRolePriority);
	}

	private void mineRoles(List<Integer[]> usersWithPermissions) {
		// find initial roles
		int hashCode = 0;
		for(Integer[] userPermissions : usersWithPermissions) {
			// ignore empty set
			if(userPermissions.length == 0) continue;
			
			hashCode = Arrays.hashCode(userPermissions);
			// check if role already exists
			if(initRoles.containsKey(hashCode)) {
				// increment count
				initRolesCount.put(hashCode, (initRolesCount.get(hashCode)) + 1);
			}
			else {
				// add initial role with count
				initRoles.put(hashCode, userPermissions);
				initRolesCount.put(hashCode, 1);
			}
		}
		// find new roles
		List<Integer> initRoleKeyList = new ArrayList(initRoles.keySet());
		Integer[] roleI, roleJ, newRole, temp;
		int newRoleHashCode;
		int initRolesSize = initRoleKeyList.size();
		
		for(int i = 0; i < initRolesSize; i++) {
			roleI = initRoles.get(initRoleKeyList.get(i));
			// intersect init roles
			for(int j = i; j < initRolesSize; j++) {
				roleJ = initRoles.get(initRoleKeyList.get(j));
				// calculate intersection if i and j
				newRole = intersectSortedArrays(roleI, roleJ);
				newRoleHashCode = Arrays.hashCode(newRole);
				// check if empty set
				if(newRole.length == 0) continue;
				genRoles.put(newRoleHashCode, newRole);
				genRolesCount.put(newRoleHashCode, 0);
			}
			// intersect all gen roles
			List<Integer[]> tempRoles = new ArrayList<Integer[]>(genRoles.values());
			for(Integer[] genRole : tempRoles) {
				// calculate intersection if i and j
				newRole = intersectSortedArrays(roleI, genRole);
				newRoleHashCode = Arrays.hashCode(newRole);
				// check if empty set
				if(newRole.length == 0) continue;
				genRoles.put(newRoleHashCode, newRole);
				genRolesCount.put(newRoleHashCode, 0);
			}
		}
		// count number of users for each gen role
		for(int genRoleKey : genRoles.keySet()) {
			for(int initRoleKey : initRoles.keySet()) {
				// check if gen role is subset of init role
				if(isStrictSubSet(genRoles.get(genRoleKey), initRoles.get(initRoleKey))) {
					genRolesCount.put(genRoleKey, genRolesCount.get(genRoleKey) + initRolesCount.get(initRoleKey));
				}
			}
		}
	}

	/**
	 * The method checks if arrA is a subset of arrB
	 */
	private boolean isStrictSubSet(Integer[] arrA, Integer[] arrB) {
		// check if arrays are equal
		if(Arrays.hashCode(arrA) == Arrays.hashCode(arrB)) {
			return false;
		}
		// check if arrA longer than B
		if(arrA.length > arrB.length) {
			return false;
		}
		// get intersection
		Integer[] intersect = intersectSortedArrays(arrA, arrB);
		// A is subset of B when intersection has equal length than A
		return intersect.length == arrA.length; 
	}

	/**
	 * Fast intersection algorithm which assumes that both arrays are sorted in ascending order.
	 */
	private Integer[] intersectSortedArrays(Integer[] arrA, Integer[] arrB) {
		int aIndex = 0;
		int bIndex = 0;
		int aLength = arrA.length;
		int bLength = arrB.length;
		// create result array long enough for full match
		List<Integer> list = new ArrayList<Integer>(Math.max(aLength, bLength));
		
		while (aIndex < aLength && bIndex < bLength) {
			// match found
			if(arrA[aIndex] == arrB[bIndex]) {
				list.add(arrA[aIndex]);
				aIndex++;
				bIndex++;
			}
			// check if current element in arr A is lower than in arr B
			else if (arrA[aIndex] < arrB[bIndex]) {
				aIndex++;
			}
			// current element in arr B is lower than in arr A
			else {
				bIndex++;
			}
		}
		
		if(list.size() == 0) return new Integer[0];
		Integer[] res = new Integer[list.size()];
		
		return list.toArray(res);
	}
	
	private TreeMap<Integer, List<Integer>> getSortedResult(int priority) {
		// sort found roles by count
		TreeMap<Integer, List<Integer>> sortedResult = new TreeMap<Integer, List<Integer>>();
		int roleCount = 0;
		List<Integer> roleList = null;
		for(Integer roleKey : genRolesCount.keySet()) {
			// get role count
			roleCount = genRolesCount.get(roleKey);
			// get original role count and prioritise
			if(initRoles.containsKey(roleKey)) {
				roleCount += initRolesCount.get(roleKey) * priority;
			}
			// check if count already exist
			roleList = sortedResult.get(roleCount);
			if(roleList == null) {
				roleList = new ArrayList<Integer>();
			}
			roleList.add(roleKey);
			// add to map
			sortedResult.put(roleCount, roleList);
		}
		
		return sortedResult;
	}
	
	public void dumpData() {
		int roleId = 0;
		System.out.println("\nComplete miner roles with permissions:");
		System.out.println("======================================");
		System.out.println("Init Roles:");
		System.out.println("-----------");
		for(Integer roleKey : initRoles.keySet()) {
			System.out.println("Init Role=" + roleId + ", permissions: " + Arrays.toString(initRoles.get(roleKey)) + 
					", count=" + initRolesCount.get(roleKey));
			roleId++;
		}
		
		System.out.println("\nGen Roles:");
		System.out.println("-----------");
		for(Integer roleKey : genRoles.keySet()) {
			System.out.println("Role=" + roleId + ", permissions: " + Arrays.toString(genRoles.get(roleKey)) + 
					", count=" + genRolesCount.get(roleKey));
			roleId++;
		}
		System.out.println("");
		
		// print sorted result
		for(int count : countSortedResult.descendingKeySet()) {
			System.out.print("count=" + count + ", roles: ");
			for(Integer roleKey : countSortedResult.get(count)) {
				System.out.print(Arrays.toString(genRoles.get(roleKey)) + ", ");
			}
			System.out.println("");
		}
	}

	public Map<Integer, Integer[]> getInitRoles() {
		return initRoles;
	}

	public Map<Integer, Integer> getInitRolesCount() {
		return initRolesCount;
	}

	public Map<Integer, Integer[]> getGenRoles() {
		return genRoles;
	}

	public Map<Integer, Integer> getGenRolesCount() {
		return genRolesCount;
	}

	public TreeMap<Integer, List<Integer>> getCountSortedResult() {
		return countSortedResult;
	}
	
}
